package com.bwt.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
	public static void main(String[] args) {
	/*	//先定义一个逆波兰表达式
		//测试1:(3+4)x5-6 =》 3 4 + 5 x 6 -	=》 29
		//测试2:(30+4)x5-6 =》 30 4 + 5 x 6 - =》 164
		//中缀表达式:4 * 5 - 8 + 60 + 8 / 2 =》后缀表达式:4 5 * 8 - 60 + 8 2 / +  => 76
		String suffixExpression = "4 5 * 8 - 60 + 8 2 / + ";
		//思路
		//1. 先将 "3 4 + 5 x 6 - " => 放到ArrayList中
		//2. 将List 传递给一个方法, 遍历之 配合栈 完成计算
		List<String> rpnList = getListString(suffixExpression);
		int res = calculate(rpnList);
		System.out.println(res);
*/

		String expression = "1+((2+3)*4)-5";
		/*[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]*/
		List<String> list = toInfixExpressionList(expression);
		System.out.println("中缀表达式对应的List = " + list);
		/*[1, 2, 3, +, 4, *, +, 5, -]*/
		List<String> suffixList = parseSuffixExpression(list);
		System.out.println("后缀表达式对应的List = " + suffixList);
		//16
		System.out.printf("expression=%d", calculate(suffixList));

	}

	public static List<String> parseSuffixExpression(List<String> list) {
		//定义两个栈
		Stack<String> s1 = new Stack<>(); // 符号栈
		//说明: 因为s2栈 在转换过程中 没有pop操作, 而且后面还需要逆序输出, 所以使用list替代
		//Stack<String> s2 = new Stack<>();
		List<String> s2 =new ArrayList<>();
		for (String item : list) {
			//如果是一个数, 加入s2
			if (item.matches("\\d+")) {
				s2.add(item);
			} else if (item.equals("(")) {
				s1.push(item);
			} else if (item.equals(")")) {
				// 如果是右括号“)”,则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
				while (!s1.peek().equals("(")) {
					s2.add(s1.pop());
				}
				// !!! 丢弃 (
				s1.pop();
			} else {
				// 当item的优先级小于等于s1栈顶运算符,
				// 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
				while (s1.size() != 0 && Operation.getValue(item) <= Operation.getValue(s1.peek())) {
					s2.add(s1.pop());
				}
				// 还需要将item压入栈
				s1.push(item);
			}
		}
		// 将s1中剩余的运算符依次弹出并加入s2
		while (s1.size() != 0) {
			s2.add(s1.pop());
		}

		// 注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
		return s2;

	}


	public static List<String> toInfixExpressionList(String s) {
		//定义一个list, 存放中缀表达式对应的内容
		List<String> list = new ArrayList<>();
		int i = 0;
		String str;
		char c;
		do {
			if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
				list.add(c + "");
				i++;
			} else {
				str = "";
				while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
					str += c;
					i++;
				}
				list.add(str);
			}
		} while (i < s.length());
		return list;
	}

	public static List<String> getListString(String suffixExpression) {
		String[] split = suffixExpression.split(" ");
		return Arrays.asList(split);
	}

	//完成对逆波兰表达式的计算
	/*
	 * 1.从左至右扫描，将3和4压入堆栈；
	 * 2.遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
	 * 3.将5入栈；
	 * 4.接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
	 * 5.将6入栈；
	 * 6.最后是-运算符，计算出35-6的值，即29，由此得出最终结果
	 */
	public static int calculate(List<String> list ) {
		//创建栈, 只需一个栈即可
		Stack<String> stack = new Stack<>();
		for (String item : list) {
			if (item.matches("\\d+")) {
				stack.push(item);
			} else {
				int num2 = Integer.parseInt(stack.pop());
				int num = Integer.parseInt(stack.pop());
				int res = 0;	//存放判断结果
				if(item.equals("+")){
					res = num + num2;
				}else if(item.equals("-")){
					res = num - num2;
				}else if(item.equals("*")){
					res = num * num2;
				}else if(item.equals("/")){
					res = num / num2;
				}else{
					throw new RuntimeException("运算符有问题！！！");
				}
				//将res入栈
				stack.push(res + "");	//整数转字符串
			}
		}
		return Integer.parseInt(stack.pop());
	}
}

class Operation {
	private static int ADD = 1;
	private static int SUB = 1;
	private static int MUL = 2;
	private static int DIV = 2;

	public static int getValue(String operation) {
		switch (operation) {
			case "+":
				return ADD;
			case "-":
				return SUB;
			case "*":
				return MUL;
			case "/":
				return DIV;
			default:
				System.out.println("不存在该运算符: " + operation);
				return 0;
		}
	}
}
